{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "第3讲 统计学习及监督学习概论\n",
    "===\n",
    "主讲教师：高鹏\n",
    "---\n",
    "办公地点：网络空间安全学院407\n",
    "---\n",
    "联系方式：pgao@qfnu.edu.cn\n",
    "---"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 兼容python2和python3\n",
    "from __future__ import print_function\n",
    "\n",
    "import numpy as np\n",
    "from numpy.linalg import inv\n",
    "import scipy as sp\n",
    "from scipy.optimize import leastsq\n",
    "import matplotlib.pyplot as plt\n",
    "%matplotlib inline"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 引言\n",
    "\n",
    "和武侠世界里一些门派分为气宗和剑宗一样，大数据科学领域也有两个不同的学派：以统计分析为基础的统计学派，以及以机器学习为基础的人工智能派。虽然这两个学派的目的都是从数据中挖掘价值，但彼此都“不服气”。\n",
    "\n",
    "- 注重模型预测效果的人工智能派认为统计学派“固步自封”，研究和使用的模型都只是一些线性模型，太过简单，根本无法处理复杂的现实数据。\n",
    "\n",
    "- 注重假设和模型解释的统计学派认为人工智能派搭建的模型缺乏理论依据、无法解释，很难帮助我们通过模型去理解数据。\n",
    "\n",
    "从历史的角度来看，一门学科出现相对立的学派通常意味着这门学科处于爆发的前夜，比如20世纪初的经济学，凯恩斯学派和新古典经济学派的长期论战极大地促进了宏观经济学的发展，并深刻地影响了各国政府的经济政策，并由此改变了人们的生活方式。现在大数据科学也处在这样相似的位置和时间节点，已经开始并将继续改变我们的世界。\n",
    "\n",
    "虽然大数据科学领域中的两个学派虽然在处理数据的方法上有很大差异，但它们有一个共同的“物质基础”——计算机。只有借助计算机强大的运算能力，我们才能在工程上实现搭建好的模型，使之发挥作用。\n",
    "\n",
    "**大数据科学是统计学、机器学习和计算机科学这3门学科的交叉**\n",
    "\n",
    "> **A data scientist is someone who is better at statistics than any software engineer and better at software engineering than any statistician**\n",
    "\n",
    "**数据科学家=懂数学的人代码写的最溜的，写代码的人数学学的最好的**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 数据科学的挑战\n",
    "\n",
    "\n",
    "## 工程实现的挑战\n",
    "\n",
    "- 在数据科学实践中，我们将使用较为复杂的机器学习或统计模型对数据做精细化的分析和预测。这在工程实现和模型搭建两方面都提出了挑战。\n",
    "\n",
    "- 数据科学在工程上的挑战可以大致分为3类：<font color=#ff0000>特征提取、矩阵运算和分布式机器学习</font>。\n",
    "    1. 一个建模项目的成功在很大程度上依赖于建模前期的特征提取。它包含<font color=#ff0000>数据清洗、数据整合、变量归一化等</font>。经过处理后，原本搅作一团的原始数据将被转换为能被模型使用的特征。这些工作需要大量的自动化程序来处理，特别是面对大数据时，因为这些大数据无法靠\"人眼\"来检查。在一个典型的建模项目中，这部分花费的时间远远大于选择和编写模型算法的时间。\n",
    "    2. 对于一个复杂的数学模型，计算机通常需要使用类似随机梯度下降法的最优化算法来估算它的模型参数。这个过程需要大量的循环，才能使参数到达收敛值附近。因此即使面对的是很小的数据集，复杂的模型也需要很长时间才能得到正确的参数估计。而且模型在结构上越复杂，需要估计的参数也就越多。对这些大量的模型参数同时做更新，在数学上对应着矩阵运算。但传统的CPU架构并不擅长做这样的运算，这导致模型训练需要耗费大量的时间。为了提高模型的训练速度，需要将相应的矩阵运算（模型参数的估算过程）移植到GPU或者特制的计算芯片上，比如TPU。\n",
    "    3. 近年来，随着分布式系统的流行和普及，存储海量数据成为了业界的标配。为了能在这海量的数据上使用复杂模型，需要将原本在一台机器上运行的模型算法改写成能在多台机器上并行运行，这也是分布式机器学习的核心内容。\n",
    "\n",
    "<p align=\"center\">\n",
    "  <img width=\"600\" src=\"Lesson3-1.jpg\">\n",
    "</p>\n",
    "\n",
    "## 模型搭建的挑战\n",
    "\n",
    "数据科学对模型搭建的要求也可以总结为3点∶模型预测效果好，模型参数是稳定且\"正确\"的、模型结果容易解释。\n",
    "\n",
    "- 模型的预测效果好，这是数据科学成功的关键。而一个模型的预测效果取决于它的假设是否被满足。从数学上来看，任何一个模型除去假设部分，它的其他推导都是严谨的数学演算，是无懈可击的。因此模型假设就是它唯一的薄弱环节。当问题场景或数据满足模型假设时，模型的效果一定不会差，反之，则预测效果就无法保证了。但在实际生产中，针对一个具体的问题，几乎不可能找到一个模型，它的假设被百分之百地满足。这时就需要避重就轻，通过特征提取等手段，尽量避免违反那些对结果影响很大的假设。这就是为什么说\"所有模型都是错的，但是，其中有一些是有用的\"。\n",
    "\n",
    "- 除了被用来对未知数据做预测外，模型另一个重要的功能就是对已有数据做分析，比如哪个变量对结果的影响最大或者某个变量对结果到底是正向影响还是负向影响等。这些分析结果在很大程度上依赖于模型参数的估计值，后者的准确与否直接决定分析结果的质量。但问题是，模型参数的估计值是不太\"可靠\"的。例如从训练数据中随机抽取两个不完全一样的数据子集A和B，然后用这两个数据集分别训练同一个模型。得到的参数估计值几乎不可能完全一样。从数学的角度来看，这说明模型参数的估计值其实是一个随机变量，具体的值取决于训练模型时使用的数据。于是我们要求这些估计值是\"正确\"的∶围绕参数真实值上下波动（也就是说它们的期望等于参数真实值）。我们还要求这些估计值是稳定的∶波动的幅度不能太大（也就是说它们的方法比较小）。这样就可以把参数估计值的\"不可靠性\"控制在可接受的范围内。\n",
    "\n",
    "- 数据科学家将模型搭建好，并不是一个数据科学项目的终点。为了充分发挥数据的价值，需要将模型结果应用到实际的生产中，比如为手机银行APP架设实时反欺诈系统，或者将利用新搭建的车祸风险模型为汽车保险定价等。参与这个过程的不仅有懂模型的数据科学家，还有更多非技术的业务人员。而后者往往是使用模型的主力，比如根据反欺诈系统的结果，对可疑用户进行人工审核，又或者向客户解释为什么他的车险比别人贵。为了帮助他们更好地理解模型结果，需要将复杂深奥的模型翻译成直观的普通语言。这要求模型是能被解释的，而且是容易被解释的。\n",
    "\n",
    "## 数据模型的搭建思路\n",
    "\n",
    "在对数据搭建模型时，有两种截然不同的思路。\n",
    "\n",
    "<p align=\"center\">\n",
    "  <img width=\"800\" src=\"Lesson3-2.jpg\">\n",
    "</p>\n",
    "\n",
    "- 数据模型（data model），也就是传统的统计模型。这种思路假设数据的产生过程是已知的（或者是可以假设的），可以通过模型去理解整个过程。因此，这类模型通常具有很好的可解释性，分析其稳定性的数学工具也很多，能很好地满足上面提到的后两点。但是在实际生产中，这些模型的预测效果并不好，或者更准确地说，单独使用时，预测效果并不理想。\n",
    "\n",
    "- 算法模型（algorithm model），也就是机器学习。这类模型是人工智能的核心内容，它们假设数据的产生过程是复杂且未知的。建模的目的是尽可能地从结构上\"模仿\"数据的产生过程，从而达到较好的预测效果。但代价是模型的可解释性很差，而且模型稳定性的分析方法也不多。\n",
    "\n",
    "正如上面的分析，统计学和机器学习在某些方面具有极好的互补性。因此在实际的生产中，为了将一个数据科学项目做得尽可能完美，我们需要将这两种思路结合起来使用。比如使用机器学习的模型对数据建模，然后借鉴数据模型的分析工具，分析模型的稳定性和给出模型结果的直观解释。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 统计（机器）学习\n",
    "\n",
    "\n",
    "## 人是如何学习的\n",
    "\n",
    "在面对一个具体的问题时，人首先会根据已有的经验和当前的信息做出反应行动，然后按照行动获得的反馈去修正自己的经验，并不断重复这个过程。\n",
    "\n",
    "我们的目的就是通过程序让计算机\"学会\"人的学习过程。换句话说， 设计一个计算机程序，这个程序能够根据\"经验\"自我完善。\n",
    "\n",
    "## 统计学习的特点\n",
    "\n",
    "统计学习（statistical learning）是关于计算机基于数据构建概率统计模型并运用模型对数据进行预测与分析的一门学科。统计学习也称为统计机器学习(statistical machine learning)。\n",
    "\n",
    "统计学习的主要特点是∶\n",
    " 1. 统计学习以计算机及网络为平台，是建立在计算机及网络之上的;\n",
    " 2. 统计学习以数据为研究对象，是数据驱动的学科;\n",
    " 3. 统计学习的目的是对数据进行预测与分析;\n",
    " 4. 统计学习以方法为中心，统计学习方法构建模型并应用模型进行预测与分析;\n",
    " 5. 统计学习是概率论、统计学、信息论、计算理论、最优化理论及计算机科学等多个领域的交叉学科，并且在发展中逐步形成独自的理论体系与方法论。\n",
    "\n",
    "赫尔伯特·西蒙（Herbert A.Simon）曾对\"学习\"给出以下定义∶\"如果一个系统能够通过执行某个过程改进它的性能，这就是学习。\"按照这一观点，统计学习就是计算机系统通过运用数据及统计方法提高系统性能的机器学习。现在，当人们提及机器学习时，往往是指统计机器学习。\n",
    "\n",
    "## 统计学习的对象\n",
    "\n",
    "统计学习的对象是<font color=#ff0000>数据（data）</font>。它从数据出发，提取数据的特征，抽象出数据的模型，发现数据中的知识，又回到对数据的分析与预测中去。作为统计学习的对象，数据是多样的，包括存在于计算机及网络上的各种数字、文字、图像、视频、音频数据以及它们的组合。\n",
    "\n",
    "统计学习关于数据的基本假设是同类数据具有一定的统计规律性，这是统计学习的前提。这里的同类数据是指具有某种共同性质的数据，例如英文文章、互联网网页、数据库中的数据等。由于它们具有统计规律性，所以可以用概率统计方法来加以处理。比如，可以用随机变量描述数据中的特征，用概率分布描述数据的统计规律。\n",
    "\n",
    "在统计学习过程中，以变量或变量组表示数据，数据分为由连续变量和离散变量表示的类型。我们仅以讨论离散变量的方法为主。另外，我们只利用数据构建模型及利用模型对数据进行分析与预测，对数据的观测和收集等问题不作讨论。\n",
    "\n",
    "## 统计学习的目的\n",
    "\n",
    "统计学习用于对数据进行预测与分析，特别是对未知新数据进行预测与分析.对数据的预测可以使计算机更加智能化，或者说使计算机的某些性能得到提高;对数据的分析可以让人们获取新的知识，给人们带来新的发现对数据的预测与分析是通过构建概率统计模型实现的。统计学习总的目标就是考虑学习什么样的模型和如何学习模型，以使模型能对数据进行准确的预测与分析，同时也要考虑尽可能地提高学习效率。\n",
    "\n",
    "## 统计学习的方法\n",
    "\n",
    "统计学习的方法是基于数据构建统计模型从而对数据进行预测与分析。统计学习由<font color=#ff0000>监督学习（supervised learning）</font>、<font color=#ff0000>非监督学习（unsupervised learning）</font>、<font color=#ff0000>半监督学习（semi-supervised learning）</font>和<font color=#ff0000>强化学习（reinforcement leaming）</font>等组成。\n",
    "\n",
    "统计学习的方法可以概括如下∶从给定的、有限的、用于学习的训练数据（training data）集合出发，假设数据是独立同分布产生的;并且假设要学习的模型属于某个函数的集合，称为假设空间（hypothesis space）;应用某个评价准则（evaluation criterion），从假设空间中选取一个最优的模型，使它对已知训练数据及未知测试数据（test data）在给定的评价准则下有最优的预测;最优模型的选取由算法实现。这样，统计学习方法包括模型的假设空间、模型选择的准则以及模型学习的算法，称其为统计学习方法的三要素，简称为<font color=#ff0000>模型（model）</font>、<font color=#ff0000>策略（strategy）</font>和<font color=#ff0000>算法（algorithm）</font>。\n",
    "\n",
    "实现统计学习方法的步骤如下∶\n",
    " 1. 得到一个有限的训练数据集合;\n",
    " 2. 确定包含所有可能的模型的假设空间，即学习模型的集合;\n",
    " 3. 确定模型选择的准则，即学习的策略;\n",
    " 4. 实现求解最优模型的算法，即学习的算法;\n",
    " 5. 通过学习方法选择最优模型;\n",
    " 6. 利用学习的最优模型对新数据进行预测或分析。\n",
    " \n",
    "## 统计学习的研究\n",
    "\n",
    "统计学习研究一般包括<font color=#ff0000>统计学习方法（statistical learning method）</font>、<font color=#ff0000>统计学习理论（statistical learning theory）</font>及<font color=#ff0000>统计学习应用（appication of stisical learning）</font>三个方面。统计学习方法的研究旨在开发新的学习方法;统计学习理论的研究在于探求统计学习方法的有效性与效率，以及统计学习的基本理论问题;统计学习应用的研究主要考虑将统计学习方法应用到实际问题中去，解决实际问题。\n",
    "\n",
    "## 统计学习的重要性\n",
    "\n",
    "近20年来，统计学习无论是在理论还是在应用方面都得到了巨大的发展，有许多重大突破，统计学习已被成功地应用到人工智能、模式识别、数据挖掘、自然语言处理、语音识别、图像识别、信息检索和生物信息等许多计算机应用领域中，并且成为这些领域的核心技术。我们确信，统计学习将会在今后的科学发展和技术应用中发挥越来越大的作用。\n",
    "\n",
    "统计学习学科在科学技术中的重要性主要体现在以下几个方面∶\n",
    " 1. 统计学习是处理海量数据的有效方法。我们处于一个信息爆炸的时代，海量数据的处理与利用是人们必然的需求。现实中的数据不但规模大，而且常常具有不确定性，统计学习往往是处理这类数据最强有力的工具。\n",
    " 2. 统计学习是计算机智能化的有效手段。智能化是计算机发展的必然趋势，也是计算机技术研究与开发的主要目标。近几十年来，人工智能等领域的研究表明，利用统计学习模仿人类智能的方法，虽有一定的局限性，但仍然是实现这一目标的最有效手段。\n",
    " 3. 统计学习是计算机科学发展的一个重要组成部分。可以认为计算机科学由三维组成;系统、计算、信息．统计学习主要属于信息这一维，并在其中起着核心作用。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 监督学习\n",
    "\n",
    "统计学习包括监督学习、非监督学习、半监督学习及强化学习。本书主要讨论监督学习问题。\n",
    "\n",
    "监督学习（supervised learning）的任务是学习一个模型，使模型能够对任意给定的输入，对其相应的输出做出一个好的预测（注意，这里的输入、输出是指某个系统的输入与输出，与学习的输入与输出不同）。计算机的基本操作就是给定一个输入产生一个输出，所以监督学习是极其重要的统计学习分支，也是统计学习中内容最丰富、应用最广泛的部分。\n",
    "\n",
    "## 基本概念\n",
    "\n",
    "### 输入空间、特征空间与输出空间\n",
    "\n",
    "在监督学习中，将输入与输出所有可能取值的集合分别称为输入空间（input space）与输出空间（output space）。输入与输出空间可以是有限元素的集合，也可以是整个欧氏空间。输入空间与输出空间可以是同一个空间，也可以是不同的空间;但通常输出空间远远小于输入空间。\n",
    "\n",
    "每个具体的输入是一个实例（instance），通常由特征向量（feature vector）表示。这时，所有特征向量存在的空间称为特征空间（feature space）。特征空间的每一维对应于一个特征。有时假设输入空间与特征空间为相同的空间，对它们不予区分;有时假设输入空间与特征空间为不同的空间，将实例从输入空间映射到特征空间.模型实际上都是定义在特征空间上的。\n",
    "\n",
    "在监督学习过程中，将输入与输出看作是定义在输入（特征）空间与输出空间上的随机变量的取值。输入、输出变量用大写字母表示，习惯上输入变量写作$X$，输出变量写作$Y$。输入、输出变量所取的值用小写字母表示，输入变量的取值写作$x$，输出变量的取值写作$y$。变量可以是标量或向量，都用相同类型字母表示。一般把向量均写为列向量，输入实例$x$的特征向量记作\n",
    "\n",
    "$$\n",
    "x=(x^{(1)},x^{(2)},、\\cdots,x^{(i)},\\cdots,x^{(n)})^T\n",
    "$$\n",
    "\n",
    "$x^{(i)}$表示$x$的第$i$个特征。注意，$x^{(i)}$与$x_{i}$不同，通常用$x_{i}$表示多个输入变量中的第$i$个，即\n",
    "\n",
    "$$\n",
    "x_{i}=(x^{(1)}_{i},x^{(2)}_{i},\\cdots,x^{(i)}_{i},\\cdots,x^{(n)}_{i})^T\n",
    "$$\n",
    "\n",
    "监督学习从训练数据（training data）集合中学习模型，对测试数据（test data）进行预测。训练数据由输入（或特征向量）与输出对组成，训练集通常表示为 \n",
    "\n",
    "$$\n",
    "T=\\{(x_1,y_1),(x_2,y_2),\\cdots,(x_N,y_N)\\}\n",
    "$$\n",
    "\n",
    "测试数据也由相应的输入与输出对组成。输入与输出对又称为样本（sample）或样本点.\n",
    "\n",
    "输入变量$X$和输出变量$Y$有不同的类型，可以是连续的，也可以是离散的。人们根据输入、输出变量的不同类型，对预测任务给予不同的名称∶输入变量与输出变量均为连续变量的预测问题称为回归问题;输出变量为有限个离散变量的预测问题称为分类问题;输入变量与输出变量均为变量序列的预测问题称为标注问题。\n",
    "\n",
    "### 联合概率分布\n",
    "\n",
    "监督学习假设输入与输出的随机变量$X$和$Y$遵循联合概率分布$P(X,Y)$。 $P(X,Y)$表示分布函数，或分布密度函数。在学习过程中，假定这一联合概率分布存在，但对学习系统来说，联合概率分布的具体定义是未知的，训练数据与测试数据被看作是依联合概率分布$P(X,Y)$独立同分布产生的．统计学习假设数据存在一定的统计规律，$X$和$Y$具有联合概率分布的假设就是监督学习关于数据的基本假设。\n",
    "\n",
    "### 假设空间\n",
    "\n",
    "监督学习的目的在于学习一个由输入到输出的映射，这一映射由模型来表示。换句话说，学习的目的就在于找到最好的这样的模型。模型属于由输入空间到输出空间的映射的集合，这个集合就是假设空间（hypothesis space）。假设空间的确定意味着学习范围的确定。\n",
    "\n",
    "监督学习的模型可以是概率模型或非概率模型，由条件概率分布$P(Y|X)$或决策函数（deision function）$Y=f(X)$表示，随具体学习方法而定。对具体的输入进行相应的输出预测时，写作$P(y|x)$或$y=f(x)$. \n",
    "\n",
    "## 问题的形式化\n",
    "\n",
    "监督学习利用训练数据集学习一个模型，再用模型对测试样本集进行预测（prediction）。由于在这个过程中需要训练数据集，而训练数据集往往是人工给出的，所以称为<font color=#ff0000>监督学习</font>。监督学习分为学习和预测两个过程，由学习系统与预测系统完成\n",
    "\n",
    "<p align=\"center\">\n",
    "  <img width=\"400\" src=\"Lesson3-3.jpg\">\n",
    "</p>\n",
    "\n",
    "首先给定一个训练数据集\n",
    "\n",
    "$$\n",
    "T=\\{(x_1,y_1),(x_2,y_2),\\cdots,(x_N,y_N)\\}\n",
    "$$\n",
    "\n",
    "其中$(x_i,y_i)$，$i=1,2,\\ldots,N$，称为样本或样本点。$x_i\\in\\mathcal{X}\\subseteq\\mathbb{R}^n$是输入的观测值，也称为输入或实例，$y_i\\in\\mathcal{Y}$是输出的观测值，也称为输出。\n",
    "\n",
    "监督学习中，假设训练数据与测试数据是依联合概率分布$P(X,Y)$独立同分布产生的。\n",
    "\n",
    "在学习过程中，学习系统利用给定的训练数据集，通过学习（或训练）得到一个模型，表示为条件概率分布$\\hat{P}(Y|X)$或决策函数$Y=\\hat{f}(X)$。条件概率分布$\\hat{P}(Y|X)$或决策函数$Y=\\hat{f}(X)$描述输入与输出随机变量之间的映射关系。\n",
    "\n",
    "在预测过程中，预测系统对于给定的测试样本集中的输入$x_{N+1}$，由模型$y_{N+1}=\\arg\\max_{y_{N+1}}\\hat{P}(y_{N+1}|x_{N+1})$或$y_{N+1}=\\hat{f}(x_{N+1})$给出相应的输出$y_{n+1}$。\n",
    "\n",
    "在学习过程中，学习系统（也就是学习算法）试图通过训练数据集中的样本$(x_i,y_i)$带来的信息学习模型。具体地说，对输入$x_i$，一个具体的模型$y=f(x)$可以产生一个输出$f(x_i)$，而训练数据集中对应的输出是$y_i$，如果这个模型有很好的预测能力，训练样本输出$y_i$和模型输出$f(x_i)$之间的差就应该足够小．学习系统通过不断的尝试，选取最好的模型，以便对训练数据集有足够好的预测，同时对未知的测试数据集的预测也有尽可能好的推广。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 统计学习三要素\n",
    "\n",
    "统计学习方法都是由模型、策略和算法构成的，即统计学习方法由三要素构成，可以简单地表示为\n",
    "\n",
    "$$\n",
    "方法=模型+策略+算法\n",
    "$$\n",
    "\n",
    "非监督学习、强化学习也同样拥有这三要素。可以说构建一种统计学习方法就是确定具体的统计学习三要素。\n",
    "\n",
    "## 模型\n",
    "\n",
    "统计学习首要考虑的问题是学习什么样的模型。在监督学习过程中，模型就是所要学习的条件概率分布或决策函数。模型的假设空间（hypothesis space）包含所有可能的条件概率分布或决策函数。例如，假设决策函数是输入变量的线性函数，那么模型的假设空间就是所有这些线性函数构成的函数集合。假设空间中的模型一般有无穷多个。假设空间用$F$表示。假设空间可以定义为决策函数的集合\n",
    "\n",
    "$$\n",
    "\\mathcal{F}={f|Y=f(X)}\n",
    "$$\n",
    "\n",
    "其中，$X$和$Y$是定义在输入空间$\\mathcal{X}$和输出空间$\\mathcal{Y}$上的变量。这时$\\mathcal{F}$通常是由一个参数向量决定的函数族\n",
    "\n",
    "$$\n",
    "\\mathcal{F}={f|Y=f_\\theta(X),\\theta\\in\\mathbb{R}^n}\n",
    "$$\n",
    "\n",
    "参数向量$\\theta$取值于$n$维欧氏空间$\\mathbb{R}^n$，称为参数空间（parameter space）。\n",
    "\n",
    "假设空间也可以定义为条件概率的集合\n",
    "\n",
    "$$\n",
    "\\mathcal{F}=\\{P|P(Y|X)\\}\n",
    "$$\n",
    "\n",
    "其中，$X$和$Y$是定义在输入空间$\\mathcal{X}$和输出空间$\\mathcal{Y}$上的随机变量。这时$\\mathcal{F}$通常是由一个参数向量决定的条件概率分布族\n",
    "\n",
    "$$\n",
    "\\mathcal{F}=\\{P|P_\\theta(Y|X),\\theta\\in\\mathbb{R}^n\\}\n",
    "$$\n",
    "\n",
    "参数向量$\\theta$取值于$n$维欧氏空间$\\mathbb{R}^n$，也称为参数空间。\n",
    "\n",
    "把由决策函数表示的模型称为非概率模型，由条件概率表示的模型为概率模型。为了简便起见，当论及模型时，有时只用其中一种模型。\n",
    "\n",
    "## 策略\n",
    "\n",
    "有了模型的假设空间，统计学习接着需要考虑的是按照什么样的准则学习或选择最优的模型。统计学习的目标在于从假设空间中选取最优模型。\n",
    "\n",
    "首先引入损失函数与风险函数的概念。损失函数度量模型一次预测的好坏，风险函数度量平均意义下模型预测的好坏。\n",
    "\n",
    "### 损失函数和风险函数\n",
    "\n",
    "监督学习问题是在假设空间$\\mathcal{F}$中选取模型$f$作为决策函数，对于给定的输入$X$，由$f(X)$给出相应的输出$Y$，这个输出的预测值$f(X)$与真实值Y可能一致也可能不一致，用一个损失函数（lossfunction）或代价函数（cost finction）来度量预测错误的程度。损失函数是$f(X)$和$Y$的非负实值函数，记作$L(Y,f(X))$。\n",
    "\n",
    "统计学习常用的损失函数有以下几种：\n",
    "\n",
    "- 0-1损失函数（0-1 loss function）\n",
    "\n",
    "$$\n",
    "L(Y,f(X))=\\left\\{\\begin{array}{ll}\n",
    "1, & Y\\neq f(X)\\\\\n",
    "0, & Y\\neq f(X)\\\n",
    "\\end{array}\\right.\\\\\n",
    "$$\n",
    "\n",
    "- 平方损失函数（quadratic loss function）\n",
    "\n",
    "$$\n",
    "L(Y,f(X))=(Y-f(X))^2\n",
    "$$\n",
    "\n",
    "- 绝对值损失函数（absolute loss function）\n",
    "\n",
    "$$\n",
    "L(Y,f(X))=|Y-f(X)|\n",
    "$$\n",
    "\n",
    "- 对数损失函数（logarithmic loss function）或对数似然损失函数（log-likelihood loss function）\n",
    "\n",
    "$$\n",
    "L(Y,P(Y|X))=-\\log P(Y|X)\n",
    "$$\n",
    "\n",
    "损失函数值越小，模型就越好。由于模型的输入、输出$(X,Y)$是随机变量，遵循联合分布$P(X,Y)，所以损失函数的期望是\n",
    "\n",
    "$$\n",
    "R_{\\exp}(f)=E_P[L(Y,f(X))]=\\int_{\\mathcal{X}\\times \\mathcal{Y}}L(y,f(x))P(x,y)dxdy\n",
    "$$\n",
    "\n",
    "这是理论上模型$f(X)$关于联合分布$P(X,Y)$的平均意义下的损失，称为风险函数（risk function）或期望损失（expected loss）。\n",
    "\n",
    "学习的目标就是选择期望风险最小的模型。由于联合分布$P(X,Y)$是未知的，$R_{exp}(f)$不能直接计算。实际上，如果知道联合分布$P(X,Y)$，可以从联合分布直接求出条件概率分布$P(Y|X)$，也就不需要学习了。正因为不知道联合概率分布，所以才需要进行学习。这样一来，一方面根据期望风险最小学习模型要用到联合分布，另一方面联合分布又是未知的，所以监督学习就成为一个病态问题（ill-formed problem）。\n",
    "\n",
    "给定一个训练数据集\n",
    "\n",
    "$$\n",
    "T=\\{(x_1,y_1),(x_2,y_2),\\ldots,(x_N,y_N)\\}\n",
    "$$\n",
    "\n",
    "模型$f(X)$关于训练数据集的平均损失称为经验风险（empirical risk）或经验损失（empirical loss），记作$R_{emp}$\n",
    "\n",
    "$$\n",
    "R_{emp}(f)=\\frac{1}{N}\\sum^N_{i=1}L(y_i,f(x_i))\n",
    "$$\n",
    "\n",
    "期望风险$R_{exp}(f)$是模型关于联合分布的期望损失，经验风险$R_{emp}(f)$是模型关于训练样本集的平均损失。根据大数定律，当样本容量$N$趋于无穷时，经验风险$R_{emp}(f)$趋于期望风险$R_{exp}(f)$。所以一个很自然的想法是用经验风险估计期望风险。但是，由于现实中训练样本数目有限，甚至很小，所以用经验风险估计期望风险常常并不理想，要对经验风险进行一定的矫正。这就关系到监督学习的两个基本策略：经验风险最小化和结构风险最小化。\n",
    "\n",
    "### 经验风险最小化与结构风险最小化\n",
    "\n",
    "在假设空间、损失函数以及训练数据集确定的情况下，经验风险函数就可以确定。经验风险最小化（empirical risk minimization，ERM）的策略认为，经验风险最小的模型是最优的模型。根据这一策略，按照经验风险最小化求最优模型就是求解最优化问题\n",
    "\n",
    "$$\n",
    "\\min_{f\\in\\mathcal{F}}\\frac{1}{N}\\sum^N_{i=1}L(y_i,f(x_i))\n",
    "$$\n",
    "\n",
    "其中，$\\mathcal{F}$是假设空间。\n",
    "\n",
    "当样本容量足够大时，经验风险最小化能保证有很好的学习效果，在现实中被广泛采用。比如，极大似然估计（maximum likelihood estimation）就是经验风险最小化的一个例子。当模型是条件概率分布，损失函数是对数损失函数时，经验风险最小化就等价于极大似然估计。\n",
    "\n",
    "但是，当样本容量很小时，经验风险最小化学习的效果就未必很好，会产生后面将要叙述的\"过拟合（over-fitting）\"现象。\n",
    "\n",
    "结构风险最小化（structural risk minimization，SRM）是为了防止过拟合而提出来的策略。结构风险最小化等价于正则化（regularization）。结构风险在经验风险上加上表示模型复杂度的正则化项（regularizer）或罚项（penalty term）。在假设空间、损失函数以及训练数据集确定的情况下，结构风险的定义是\n",
    "\n",
    "$$\n",
    "R_{srm}(f)=\\frac{1}{N}\\sum^N_{i=1}L(y_i,f(x_i))+\\lambda J(f)\n",
    "$$\n",
    "\n",
    "其中$J(f)$为模型的复杂度，是定义在假设空间$\\mathcal{F}$上的泛函．模型$f$越复杂，复杂度$J(f)$就越大;反之，模型$f$越简单，复杂度$J(f)$就越小。也就是说，复杂度表示了对复杂模型的惩罚。$\\lambda\\geq 0$是系数，用以权衡经验风险和模型复杂度。结构风险小需要经验风险与模型复杂度同时小。结构风险小的模型往往对训练数据以及未知的测试数据都有较好的预测。\n",
    "\n",
    "比如，贝叶斯估计中的最大后验概率估计（maximum posterior probability estimation，MAP）就是结构风险最小化的一个例子。当模型是条件概率分布、损失函数是对数损失函数、模型复杂度由模型的先验概率表示时，结构风险最小化就等价于最大后验概率估计。\n",
    "\n",
    "结构风险最小化的策略认为结构风险最小的模型是最优的模型。所以求最优模型，就是求解最优化问题\n",
    "\n",
    "$$\n",
    "\\min_{f\\in\\mathcal{F}}\\frac{1}{N}\\sum^N_{i=1}L(y_i,f(x_i))+\\lambda j(f)\n",
    "$$\n",
    "\n",
    "这样，监督学习问题就变成了经验风险或结构风险函数的最优化问题。这时经验或结构风险函数是最优化的目标函数。\n",
    "\n",
    "## 算法\n",
    "\n",
    "算法是指学习模型的具体计算方法。统计学习基于训练数据集，根据学习策略，从假设空间中选择最优模型，最后需要考虑用什么样的计算方法求解最优模型。\n",
    "\n",
    "这时，统计学习问题归结为最优化问题，统计学习的算法成为求解最优化问题的算法。如果最优化问题有显式的解析解，这个最优化问题就比较简单。但通常解析解不存在，这就需要用数值计算的方法求解。如何保证找到全局最优解，并使求解的过程非常高效，就成为一个重要问题。统计学习可以利用已有的最优化算法，有时也需要开发独自的最优化算法。\n",
    "\n",
    "**统计学习方法之间的不同，主要来自其模型、策略、算法的不同。确定了模型、策略、算法，统计学习的方法也就确定了。这也就是将其称为统计学习三要素的原因。**"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 模型评估与模型选择\n",
    "\n",
    "## 训练误差与测试误差\n",
    "\n",
    "统计学习的目的是使学到的模型不仅对已知数据而且对未知数据都能有很好的预测能力。不同的学习方法会给出不同的模型。当损失函数给定时，基于损失函数的模型的训练误差（training error）和模型的测试误差（test error）就自然成为学习方法评估的标准。\n",
    "- 注意，统计学习方法具体采用的损失函数未必是评估时使用的损失函数。\n",
    "- 当然，让两者一致是比较理想的。\n",
    "\n",
    "假设学习到的模型是$Y=\\hat{f}(X)$，训练误差是模型$Y=\\hat{f}(X)$关于训练数据集的平均损失\n",
    "\n",
    "$$\n",
    "R_{emp}(\\hat{f})=\\frac{1}{N}\\sum^N_{i=1}L(y_i,\\hat{f}(x_i))\n",
    "$$\n",
    "\n",
    "其中$N$是训练样本。\n",
    "\n",
    "测试误差是模型$Y=\\hat{f}(X)$关于测试数据集的平均损失\n",
    "\n",
    "$$\n",
    "e_{test}=\\frac{1}{n^\\prime}\\sum_{i=1}^{N^\\prime}L(y_i,\\hat{f}(x_i))\n",
    "$$\n",
    "\n",
    "其中$N^\\prime$是测试样本容量。\n",
    "\n",
    "例如，当损失函数是0-1损失时，测试误差就变成了常见的测试数据集上的误差率（error rate）\n",
    "\n",
    "$$\n",
    "e_{test}=\\frac{1}{n^\\prime}\\sum_{i=1}^{N^\\prime}I(y_i\\neq\\hat{f}(x_i))\n",
    "$$\n",
    "\n",
    "这里$I$是指示函数（indicator function），即$y\\neq\\hat{f}(x)$时为$1$，否则为$0$。\n",
    "\n",
    "相应地，常见的测试数据集上的准确率（accuracy）为\n",
    "\n",
    "$$\n",
    "r_{test}=\\frac{1}{N^\\prime}\\sum^{N^\\prime}_{i=1}I(y_i=\\hat{f}(x_i))\n",
    "$$\n",
    "\n",
    "显然\n",
    "\n",
    "$$\n",
    "r_{test}+e{test}=1\n",
    "$$\n",
    "\n",
    "训练误差的大小，对判断给定的问题是不是一个容易学习的问题是有意义的，但本质上不重要。测试误差反映了学习方法对未知的测试数据集的预测能力，是学习中的重要概念。显然，给定两种学习方法，测试误差小的方法具有更好的预测能力，是更有效的方法。通常将学习方法对未知数据的预测能力称为泛化能力（generalization ability）。\n",
    "\n",
    "## 过拟合与模型选择\n",
    "\n",
    "当假设空间含有不同复杂度（例如，不同的参数个数）的模型时，就要面临模型选择（model selection）的问题，我们希望选择或学习一个合适的模型。如果在假设空间中存在\"真\"模型，那么所选择的模型应该逼近真模型。具体地，所选择的模型要与真模型的参数个数相同，所选择的模型的参数向量与真模型的参数向量相近。\n",
    "\n",
    "如果一味追求提高对训练数据的预测能力，所选模型的复杂度则往往会比真模型更高。这种现象称为过拟合（over-fitig）。过拟合是指学习时选择的模型所包含的参数过多，以致于出现这一模型对已知数据预测得很好，但对未知数据预测得很差的现象。可以说模型选择旨在避免过拟合并提高模型的预测能力。下面，以多项式函数拟合问题为例，说明过拟合与模型选择。这是一个回归问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 例\n",
    "\n",
    "假设给定一个训练数据集\n",
    "\n",
    "$$\n",
    "T=\\{(x_1,y_1),(x_2,y_2),\\ldots\\,(x_N,y_N)\\}\n",
    "$$\n",
    "\n",
    "其中，$x_i\\in\\mathbb{R}$是输入$x$的观测值，$y_i\\in\\mathbb{R}$是相应的输出$y$的观测值，$i=1,2,\\ldots,N$。多项式函数拟合的任务是假设给定数据由$M$次多项式函数生成，选择最有可能产生这些数据的$M$次多项式函数，即在$M$次多项式函数中选择一个对已知数据以及未知数据都有很好预测能力的函数。\n",
    "\n",
    "假设给定如图所示的10个数据点，用0～9次多项式函数对数据进行拟合（目标函数$y=sin2{\\pi}x$, 加上一个正态分布的噪音干扰）。图中画出了需要用多项式函数曲线拟合的数据。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 目标函数 \n",
    "def real_func(x):\n",
    "    return np.sin(2*np.pi*x)\n",
    "\n",
    "# 多项式\n",
    "def fit_func(p, x):\n",
    "    f = np.poly1d(p)\n",
    "    return f(x)\n",
    "\n",
    "# 残差\n",
    "def residuals_func(p, x, y):\n",
    "    ret = fit_func(p, x) - y\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 十个点\n",
    "x = np.linspace(0, 1, 10)\n",
    "x_points = np.linspace(0, 1, 1000)\n",
    "# 加上正态分布噪音的目标函数的值\n",
    "y_ = real_func(x)\n",
    "y = [np.random.normal(0, 0.1)+y1 for y1 in y_]\n",
    "\n",
    "plt.plot(x_points, real_func(x_points), label='real')\n",
    "plt.plot(x, y, 'bo', label='noise')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "设$M$次多项式为\n",
    "\n",
    "$$\n",
    "f_M(x,w)=w_0+w_1x+w_2x^2+\\cdots+w_Mx^M=\\Sigma^M_{j=0}w_jx^j\n",
    "$$\n",
    "\n",
    "式中$x$是单变量输入，$w_0$，$w_1$，$\\ldots$，$w_M$是$M+1$个参数。\n",
    "\n",
    "解决这一问题的方法可以是这样的。首先确定模型的复杂度，即确定多项式的次数;然后在给定的模型复杂度下，按照经验风险最小化的策略，求解参数，即多项式的系数，具体地，求以下经验风险最小化\n",
    "\n",
    "$$\n",
    "L(w)=\\frac{1}{2}\\sum^N_{i=1}(f(x_i,w)-y_i)^2\n",
    "$$\n",
    "\n",
    "上式损失函数为平方损失，系数$\\frac{1}{2}$是为了计算方便。\n",
    "\n",
    "这是一个简单的最优化问题。将模型与训练数据代入上式\n",
    "\n",
    "$$\n",
    "L(w)=\\frac{1}{2}\\sum^N_{i=1}(\\sum^M_{j=0}w_jx_i^j-y_i)^2\n",
    "$$\n",
    "\n",
    "对$w_j$求偏导数并令其为0\n",
    "\n",
    "$$\n",
    "w_j=\\frac{\\sum^N_{i=1}x_iy_i}{\\sum^N_{i=1}x_i^{j+1}},\\quad j=0,1,2,\\cdots,M\n",
    "$$\n",
    "\n",
    "可求得拟合多项式系数$w_0^*$，$w_1^*$，$\\ldots$，$w_M^*$。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下面给出$M=0$，$M=1$，$M=3$及$M=9$时多项式函数拟合的情况。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fitting(M=0):\n",
    "    \"\"\"\n",
    "    M 为多项式的次数\n",
    "    \"\"\"    \n",
    "    # 随机初始化多项式参数\n",
    "    p_init = np.random.rand(M+1)\n",
    "    # 最小二乘法\n",
    "    p_lsq = leastsq(residuals_func, p_init, args=(x, y))\n",
    "    print('Fitting Parameters:', p_lsq[0])\n",
    "    \n",
    "    # 可视化\n",
    "    plt.plot(x_points, real_func(x_points), label='real')\n",
    "    plt.plot(x_points, fit_func(p_lsq[0], x_points), label='fitted curve')\n",
    "    plt.plot(x, y, 'bo', label='noise')\n",
    "    plt.legend()\n",
    "    return p_lsq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果$M=0$，多项式曲线是一个常数，数据拟合效果很差"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# M=0\n",
    "p_lsq_0 = fitting(M=0)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果$M=1$，多项式曲线是一条直线，数据拟合效果也很差"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# M=1\n",
    "p_lsq_1 = fitting(M=1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "如果$M=9$，多项式曲线通过每个数据点，训练误差为0。从对给定训练数据拟合的角度来说，效果是最好的。但是，因为训练数据本身存在噪声，这种拟合曲线对未知数据的预测能力往往并不是最好的，在实际学习中并不可取。这时过拟合现象就会发生，这就是说，模型选择时，不仅要考虑对已知数据的预测能力，而且还要考虑对未知数据的预测能"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true,
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "# M=9\n",
    "p_lsq_9 = fitting(M=9)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "当$M=3$时，多项式曲线对训练数据拟合效果足够好，模型也比较简单，是一个较好的选择"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# M=3\n",
    "p_lsq_3 = fitting(M=3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在多项式函数拟合中可以看到，随着多项式次数（模型复杂度）的增加，训练误差会减小，直至趋向于0，但是测试误差却不如此，它会随着多项式次数（模型复杂度）的增加先减小而后增大。而最终的目的是使测试误差达到最小。这样，在多项式函数拟合中，就要选择合适的多项式次数，以达到这一目的。这一结论对一般的模型选择也是成立的。\n",
    "\n",
    "<p align=\"center\">\n",
    "  <img width=\"400\" src=\"Lesson3-4.jpg\">\n",
    "</p>\n",
    "\n",
    "上图描述了训练误差和测试误差与模型的复杂度之间的关系。当模型的复杂度增大时，训练误差会逐渐减小并趋向于0;而测试误差会先减小，达到最小值后又增大。当选择的模型复杂度过大时，过拟合现象就会发生。这样，在学习时就要防止过拟合，进行最优的模型选择，即选择复杂度适当的模型，以达到使测试误差最小的学习目的。下面介绍两种常用的模型选择方法∶正则化与交叉验证。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 正则化\n",
    "\n",
    "模型选择的典型方法是正则化（regularization）。正则化是结构风险最小化策略的实现，是在经验风险上加一个正则化项（regularizer）或罚项（penalty term）。正则化项一般是模型复杂度的单调递增函数，模型越复杂，正则化值就越大。比如，正则化项可以是模型参数向量的范数。\n",
    "\n",
    "正则化一般具有如下形式\n",
    "\n",
    "$$\n",
    "\\min_{f\\in\\mathcal{F}}\\frac{1}{N}\\sum^N_{i=1}L(y_i,f(x_i))+\\lambda J(f)\n",
    "$$\n",
    "\n",
    "其中，第1项是经验风险，第2项是正则化项，$\\lambda\\geq0$为调整两者之间关系的系数。\n",
    "\n",
    "正则化项可以取不同的形式。例如，回归问题中，损失函数是平方损失，正则化项可以是参数向量的$L_2$范数\n",
    "\n",
    "$$\n",
    "L(w)=\\frac{1}{N}\\sum^N_{i=1}(f(x_i;w)-y_i)^2+\\frac{\\lambda}{2}||w||_2^2\n",
    "$$\n",
    "\n",
    "这里$||w||_2$表示参数向量$w$的$L_2$范数。\n",
    "\n",
    "正则化项也可以是参数向量的$L_1$范数\n",
    "\n",
    "$$\n",
    "L(w)=\\frac{1}{N}\\sum^N_{i=1}(f(x_i;w)-y_i)^2+\\lambda||w||_1\n",
    "$$\n",
    "\n",
    "这里$||w||_1$表示参数向量$w$的$L_1$范数。\n",
    "\n",
    "第1项的经验风险较小的模型可能较复杂（有多个非零参数），这时第2项的模型复杂度会较大。正则化的作用是选择经验风险与模型复杂度同时较小的模型。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "regularization = 0.0001\n",
    "\n",
    "def residuals_func_regularization(p, x, y):\n",
    "    ret = fit_func(p, x) - y\n",
    "    ret = np.append(ret, np.sqrt(0.5*regularization*np.square(p))) # L2范数作为正则化项\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 最小二乘法,加正则化项\n",
    "p_init = np.random.rand(9+1)\n",
    "p_lsq_regularization = leastsq(residuals_func_regularization, p_init, args=(x, y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "plt.plot(x_points, real_func(x_points), label='real')\n",
    "plt.plot(x_points, fit_func(p_lsq_9[0], x_points), label='fitted curve')\n",
    "plt.plot(x_points, fit_func(p_lsq_regularization[0], x_points), label='regularization')\n",
    "plt.plot(x, y, 'bo', label='noise')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "regularization = 0.0001\n",
    "\n",
    "def residuals_func_regularization(p, x, y):\n",
    "    ret = fit_func(p, x) - y\n",
    "    ret = np.append(ret, np.sqrt(regularization*abs(p))) # L1范数作为正则化项\n",
    "    return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# 最小二乘法,加正则化项\n",
    "p_init = np.random.rand(9+1)\n",
    "p_lsq_regularization = leastsq(residuals_func_regularization, p_init, args=(x, y))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "plt.plot(x_points, real_func(x_points), label='real')\n",
    "plt.plot(x_points, fit_func(p_lsq_9[0], x_points), label='fitted curve')\n",
    "plt.plot(x_points, fit_func(p_lsq_regularization[0], x_points), label='regularization')\n",
    "plt.plot(x, y, 'bo', label='noise')\n",
    "plt.legend()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "正则化符合奥卡姆剃刀（Occam's razor）原理。奥卡姆剃刀原理应用于模型选择时变为以下想法∶在所有可能选择的模型中，能够很好地解释已知数据并且十分简单才是最好的模型，也就是应该选择的模型。从贝叶斯估计的角度来看，正则化项对应于模型的先验概率，可以假设复杂的模型有较大的先验概率，简单的模型有较小的先验概率。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 交叉验证\n",
    "\n",
    "另一种常用的模型选择方法是交叉验证（cross validation）。\n",
    "\n",
    "如果给定的样本数据充足，进行模型选择的一种简单方法是随机地将数据集切分成三部分，分别为训练集（training set）、验证集（validation set）和测试集（test set）。训练集用来训练模型，验证集用于模型的选择，而测试集用于最终对学习方法的评估。在学习到的不同复杂度的模型中，选择对验证集有最小预测误差的模型。由于验证集有足够多的数据，用它对模型进行选择也是有效的。\n",
    "\n",
    "但是，在许多实际应用中数据是不充足的．为了选择好的模型，可以采用交叉验证方法。交叉验证的基本想法是重复地使用数据;把给定的数据进行切分，将切分的数据集组合为训练集与测试集，在此基础上反复地进行训练、测试以及模型选择。\n",
    "\n",
    "## 简单交叉验证\n",
    "\n",
    "简单交叉验证方法是∶首先随机地将已给数据分为两部分，一部分作为训练集，另一部分作为测试集（例如，70%的数据为训练集，30%的数据为测试集）;然后用训练集在各种条件下（例如，不同的参数个数）训练模型，从而得到不同的模型;在测试集上评价各个模型的测试误差，选出测试误差最小的模型。\n",
    "\n",
    "## S折交叉验证\n",
    "\n",
    "应用最多的是S折交叉验证（S-fold cross validation），方法如下∶首先随机地将已给数据切分为S个互不相交的大小相同的子集;然后利用S-1个子集的数据训练模型，利用余下的子集测试模型;将这一过程对可能的S种选择重复进行;最后选出S次评测中平均测试误差最小的模型。\n",
    "\n",
    "## 留一交叉验证\n",
    "\n",
    "S折交叉验证的特殊情形是$S=N$，称为留一交叉验证（leave-one-out cross validation），往往在数据缺乏的情况下使用。这里，N是给定数据集的容量。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 生成模型与判别模型\n",
    "\n",
    "监督学习的任务就是学习一个模型，应用这一模型，对给定的输入预测相应的输出.这个模型的一般形式为决策函数\n",
    "\n",
    "$$\n",
    "Y=f(X)\n",
    "$$\n",
    "\n",
    "或者条件概率分布\n",
    "\n",
    "$$\n",
    "P(Y|X)\n",
    "$$\n",
    "\n",
    "监督学习方法又可以分为生成方法（generative aproach）和判别方法（discriminative approach），所学到的模型分别称为生成模型（generative model）和判别模型（discriminative model）。\n",
    "\n",
    "生成方法由数据学习联合概率分布$P(X,Y)$，然后求出条件概率分布$P(Y|X)$作为预测的模型，即生成模型\n",
    "\n",
    "$$\n",
    "P(Y|X)=\\frac{P(X,Y)}{P(X)}\n",
    "$$\n",
    "\n",
    "这样的方法之所以称为生成方法，是因为模型表示了给定输入X产生输出Y的生成关系．典型的生成模型有∶朴素贝叶斯法和隐马尔可夫模型。\n",
    "\n",
    "判别方法由数据直接学习决策函数$f(X)$或者条件概率分布$P(Y|X)$作为预测的模型，即判别模型。判别方法关心的是对给定的输入$X$，应该预测什么样的输出$Y$．典型的判别模型包括∶k近邻法、感知机、决策树、逻辑斯谛回归模型、最大熵模型、支持向量机、提升方法和条件随机场等。\n",
    "\n",
    "在监督学习中，生成方法和判别方法各有优缺点，适合于不同条件下的学习问题。\n",
    "\n",
    "生成方法的特点∶生成方法可以还原出联合概率分布$P(X,Y)$，而判别方法则不能;生成方法的学习收敛速度更快，即当样本容量增加的时候，学到的模型可以更快地收敛于真实模型;当存在隐变量时，仍可以用生成方法学习，此时判别方法就不能用。\n",
    "\n",
    "判别方法的特点∶判别方法直接学习的是条件概率$P(Y|X)$或决策函数$f(X)$，直接面对预测，往往学习的准确率更高;由于直接学习$P(Y|X)$或$f(X)$，可以对数据进行各种程度上的抽象、定义特征并使用特征，因此可以简化学习问题。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 分类问题\n",
    "\n",
    "分类是监督学习的一个核心问题。在监督学习中，当输出变量$Y$取有限个离散值时，预测问题便成为分类问题。这时，输入变量$X$可以是离散的，也可以是连续的。监督学习从数据中学习一个分类模型或分类决策函数，称为分类器（classifier）。分类器对新的输入进行输出的预测（prediction），称为分类（classification），可能的输出称为类（class）。分类的类别为多个时，称为多类分类问题.本书主要讨论二类分类问题。\n",
    "\n",
    "分类问题包括学习和分类两个过程.在学习过程中，根据已知的训练数据集利用有效的学习方法学习一个分类器;在分类过程中，利用学习的分类器对新的输入实例进行分类．分类问题中，$(x_1,y_1),(x_2,y_2),\\ldots,(x_N,y_N)$是训练数据集，学习系统由训练数据学习一个分类器$P(Y|X)$或$Y=f(X)$;分类系统通过学到的分类器$P(Y|X)$或$Y=f(X)$对于新的输入实例$x$进行分类，即预测其输出的类标记$y_{N+1}$\n",
    "\n",
    "<p align=\"center\">\n",
    "  <img width=\"400\" src=\"Lesson3-5.jpg\">\n",
    "</p>\n",
    "\n",
    "评价分类器性能的指标一般是分类准确率（accuracy），其定义是：对于给定的测试数据集，分类器正确分类的样本数与总样本数之比。也就是损失函数是0-1损失时测试数据集上的准确率。\n",
    "\n",
    "对于二类分类问题常用的评价指标是精确率（precision）与召回率（recall）。通常以关注的类为正类，其他类为负类，分类器在测试数据集上的预测或正确或不正确，4种情况出现的总数分别记作：\n",
    "\n",
    "1. TP——将正类预测为正类数\n",
    "2. FN——将正类预测为负类数\n",
    "3. FP——将负类预测为正类数\n",
    "4. TN——将负类预测为负类数\n",
    "\n",
    "精确率定义为\n",
    "\n",
    "$$\n",
    "P=\\frac{TP}{TP+FP}\n",
    "$$\n",
    "\n",
    "召回率定义为\n",
    "\n",
    "$$\n",
    "R=\\frac{TP}{TP+FN}\n",
    "$$\n",
    "\n",
    "此外，还有$F_1$值，是精确率和召回率的调和均值，即\n",
    "\n",
    "$$\n",
    "\\frac{2}{F_1}=\\frac{1}{P}+\\frac{1}{R}\n",
    "$$\n",
    "\n",
    "$$\n",
    "F_1=\\frac{2TP}{2TP+FP+FN}\n",
    "$$\n",
    "\n",
    "精确率和召回率都高时，$F_1$值也会高。\n",
    "\n",
    "许多统计学习方法可以用于分类，包括k近邻法、感知机、朴素贝叶斯法、决策树、决策列表、逻辑斯谛回归模型、支持向量机、提升方法、贝叶斯网络、神经网络等。\n",
    "\n",
    "分类在于根据其特性将数据\"分门别类\"，所以在许多领域都有广泛的应用。例如，在银行业务中，可以构建一个客户分类模型，对客户按照贷款风险的大小进行分类;在网络安全领域，可以利用日志数据的分类对非法入侵进行检测;在图像处理中，分类可以用来检测图像中是否有人脸出现;在手写识别中，分类可以用于识别手写的数字;在互联网搜索中，网页的分类可以帮助网页的抓取、索引与排序。\n",
    "\n",
    "举一个分类应用的例子——文本分类（text classification）。这里的文本可以是新闻报道、网页、电子邮件、学术论文等。类别往往是关于文本内容的，例如政治、经济、体育等;也有关于文本特点的，如正面意见、反面意见;还可以根据应用确定，如垃圾邮件、非垃圾邮件等。文本分类是根据文本的特征将其划分到已有的类中。输入是文本的特征向量，输出是文本的类别。通常把文本中的单词定义为特征，每个单词对应一个特征。单词的特征可以是二值的，如果单词在文本中出现则取值是1，否则是0;也可以是多值的，表示单词在文本中出现的频率。直观地，如果\"股票\"\"银行\"\"货币\"这些词出现很多，这个文本可能属于经济类，如果\"网球\"\"比赛\"\"运动员\"这些词频繁出现，这个文本可能属于体育类。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 标注问题\n",
    "\n",
    "标注（tagging）也是一个监督学习问题。可以认为标注问题是分类问题的一个推广，标注问题又是更复杂的结构预测（structure prediction）问题的简单形式。标注问题的输入是一个观测序列，输出是一个标记序列或状态序列。标注问题的目标在于学习一个模型，使它能够对观测序列给出标记序列作为预测。注意，可能的标记个数是有限的，但其组合所成的标记序列的个数是依序列长度呈指数级增长的。\n",
    "\n",
    "标注问题分为学习和标注两个过程。首先给定一个训练数据集$T=\\{(x_1,y_1),(x_2,x_2),\\ldots,(x_N,y_N)\\}$\n",
    "\n",
    "这里，$x_i=(x_i^{(1)},x_i^{(2)},\\ldots,x_i^{(n)})^T$，$i=1,2,\\ldots,N$，是输入观测序列，$y_i=(y_i^{(1)},y_i^{(2)},\\ldots,y_i^{(n)})^T$是相应的输出标记序列，n是序列的长度，对不同样本可以有不同的值。学习系统基于训练数据集构建一个模型，表示为条件概率分布\n",
    "\n",
    "$$\n",
    "P(Y^{(1)},Y^{(2)},\\ldots,Y^{(n)}|X^{(1)},X^{(2)},\\ldots,X^{(n)})\n",
    "$$\n",
    "\n",
    "这里，每一个$X^{(i)}(i=1,2,\\ldots,n)$取值为所有可能的观测，每一个$Y^{(i)}(i=1,2,\\ldots,n)$取值为所有可能的标记，一般$n\\ll N$．标注系统按照学习得到的条件概率分布模型，对新的输入观测序列找到相应的输出标记序列。具体地，对一个观测序列$x_{N+1}=(x_{N+1}^{(1)},x_{N+1}^{(2)},\\ldots,x_{N+1}^{(n)})^T$找到使条件概率$P((y_{N+1}^{(1)},y_{N+1}^{(2)},\\ldots,y_{N+1}^{(n)})^T|(x_{N+1}^{(1)},x_{N+1}^{(2)},\\ldots,x_{N+1}^{(n)})^T)$最大的标记序列$y_{N+1}=(y_{N+1}^{(1)},y_{N+1}^{(2)},\\ldots,y_{N+1}^{(n)})^T$。\n",
    "\n",
    "评价标注模型的指标与评价分类模型的指标一样，常用的有标注准确率、精确率和召回率。其定义与分类模型相同。\n",
    "\n",
    "标注常用的统计学习方法有：隐马尔可夫模型、条件随机场。\n",
    "\n",
    "标注问题在信息抽取、自然语言处理等领域被广泛应用，是这些领域的基本问题。例如，自然语言处理中的词性标注（part of speech tagging）就是一个典型的标注问题：给定一个由单词组成的句子，对这个句子中的每一个单词进行词性标注，即对一个单词序列预测其对应的词性标记序列。\n",
    "\n",
    "举一个信息抽取的例子。从英文文章中抽取基本名词短语（base noun phrase），为此，要对文章进行标注。英文单词是一个观测，英文句子是一个观测序列，标记表示名词短语的\"开始\"、\"结束\"或\"其他\"（分别以B，E，O表示），标记序列表示英文句子中基本名词短语的所在位置。信息抽取时，将标记\"开始\"到标记\"结束\"的单词作为名词短语。例如，给出以下的观测序列，即英文句子，标注系统产生相应的标记序列，即给出句子中的基本名词短语。\n",
    "\n",
    "- 输入：At Microsoft Research， we have an insatiable curiosity and the desire to create new technology that will help define the computing experience.\n",
    "- 输出∶ At/O Microsof/B Research/E， we/O have/O an/O insatiable/B curiosity/E and/O the/O desire/BE to/O create/Onew/B technology/E that/O will/O help/O define/O the/O computing/B experience/E."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 回归问题\n",
    "\n",
    "回归（regression）是监督学习的另一个重要问题。回归用于预测输入变量（自变量）和输出变量（因变量）之间的关系，特别是当输入变量的值发生变化时，输出变量的值随之发生的变化。回归模型正是表示从输入变量到输出变量之间映射的函数。回归问题的学习等价于函数拟合;选择一条函数曲线使其很好地拟合已知数据且很好地预测未知数据。\n",
    "\n",
    "回归问题分为学习和预测两个过程。首先给定一个训练数据集\n",
    "\n",
    "$$\n",
    "T=\\{(x_1,y_1),(x_2,y_2),\\ldots,(x_N,y_N)\\}\n",
    "$$\n",
    "\n",
    "这里，$x_i\\in\\mathbb{R}^n$是输入，$y\\in\\mathbb{R}$是对应的输出，$i=1,2,\\ldots,N$。学习系统基于训练数据构建一个模型，即函数$Y=f(X)$;对新的输入$x_{N+1}$，预测系统根据学习的模型$Y=f(X)$确定相应的输出$y_{N+1}$\n",
    "\n",
    "<p align=\"center\">\n",
    "  <img width=\"400\" src=\"Lesson3-6.jpg\">\n",
    "</p>\n",
    "\n",
    "回归问题按照输入变量的个数，分为一元回归和多元回归;按照输入变量和输出变量之间关系的类型即模型的类型，分为线性回归和非线性回归。\n",
    "\n",
    "回归学习最常用的损失函数是平方损失函数，在此情况下，回归问题可以由著名的最小二乘法（leas quares）求解。\n",
    "\n",
    "许多领域的任务都可以形式化为回归问题，比如，回归可以用于商务领域，作为市场趋势预测、产品质量管理、客户满意度调查、投资风险分析的工具。作为例子，简单介绍股价预测问题。假设知道某一公司在过去不同时间点（比如，每天）的市场上的股票价格（比如，股票平均价格），以及在各个时间点之前可能影响该公司股价的信息（比如，该公司前一周的营业额、利润）。目标是从过去的数据学习一个模型，使它可以基于当前的信息预测该公司下一个时间点的股票价格。可以将这个问题作为回归问题解决。具体地，将影响股价的信息视为自变量（输入的特征），而将股价视为因变量（输出的值）。将过去的数据作为训练数据，就可以学习一个回归模型，并对未来的股价进行预测。可以看出这是一个困难的预测问题，因为影响股价的因素非常多，我们未必能判断到哪些信息（输入的特征）有用并能得到这些信息。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 思考1\n",
    "\n",
    "说明伯努利模型的极大似然估计以及贝叶斯估计中的统计学习方法三要素。伯努利模型是定义在取值为0与1的随机变量上的概率分布。假设观测到伯努利模型$n$次独立的数据生成结果，其中$k$次的结果为1，这时可以用极大似然估计或贝叶斯估计来估计结果为1的概率。\n",
    "\n",
    "**解答：**\n",
    "\n",
    "伯努利模型的极大似然估计以及贝叶斯估计中的**统计学习方法三要素**如下：  \n",
    "1. **极大似然估计**  \n",
    "**模型：** $\\mathcal{F}=\\{f|f_p(x)=p^x(1-p)^{(1-x)}\\}$  \n",
    "**策略：** 最大化似然函数  \n",
    "**算法：** $\\displaystyle \\mathop{\\arg\\min}_{p} L(p)= \\mathop{\\arg\\min}_{p} \\binom{n}{k}p^k(1-p)^{(n-k)}$\n",
    "2. **贝叶斯估计**  \n",
    "**模型：** $\\mathcal{F}=\\{f|f_p(x)=p^x(1-p)^{(1-x)}\\}$  \n",
    "**策略：** 求参数期望  \n",
    "**算法：**\n",
    "$$\\begin{aligned}  E_\\pi\\big[p \\big| y_1,\\cdots,y_n\\big]\n",
    "& = {\\int_0^1}p\\pi (p|y_1,\\cdots,y_n) dp \\\\\n",
    "& = {\\int_0^1} p\\frac{f_D(y_1,\\cdots,y_n|p)\\pi(p)}{\\int_{\\Omega}f_D(y_1,\\cdots,y_n|p)\\pi(p)dp}dp \\\\\n",
    "& = {\\int_0^1}\\frac{p^{k+1}(1-p)^{(n-k)}}{\\int_0^1 p^k(1-p)^{(n-k)}dp}dp\n",
    "\\end{aligned}$$\n",
    "\n",
    "**伯努利模型的极大似然估计：**  \n",
    "定义$P(Y=1)$概率为$p$，可得似然函数为：$$L(p)=f_D(y_1,y_2,\\cdots,y_n|\\theta)=\\binom{n}{k}p^k(1-p)^{(n-k)}$$方程两边同时对$p$求导，则：$$\\begin{aligned}\n",
    "0 & = \\binom{n}{k}[kp^{k-1}(1-p)^{(n-k)}-(n-k)p^k(1-p)^{(n-k-1)}]\\\\\n",
    "& = \\binom{n}{k}[p^{(k-1)}(1-p)^{(n-k-1)}(m-kp)]\n",
    "\\end{aligned}$$可解出$p$的值为$p=0,p=1,p=k/n$，显然$\\displaystyle P(Y=1)=p=\\frac{k}{n}$  \n",
    "\n",
    "**伯努利模型的贝叶斯估计：**  \n",
    "定义$P(Y=1)$概率为$p$，$p$在$[0,1]$之间的取值是等概率的，因此先验概率密度函数$\\pi(p) = 1$，可得似然函数为： $$L(p)=f_D(y_1,y_2,\\cdots,y_n|\\theta)=\\binom{n}{k}p^k(1-p)^{(n-k)}$$  \n",
    "根据似然函数和先验概率密度函数，可以求解$p$的条件概率密度函数：$$\\begin{aligned}\\pi(p|y_1,\\cdots,y_n)&=\\frac{f_D(y_1,\\cdots,y_n|p)\\pi(p)}{\\int_{\\Omega}f_D(y_1,\\cdots,y_n|p)\\pi(p)dp}\\\\\n",
    "&=\\frac{p^k(1-p)^{(n-k)}}{\\int_0^1p^k(1-p)^{(n-k)}dp}\\\\\n",
    "&=\\frac{p^k(1-p)^{(n-k)}}{B(k+1,n-k+1)}\n",
    "\\end{aligned}$$所以$p$的期望为：$$\\begin{aligned}\n",
    "E_\\pi[p|y_1,\\cdots,y_n]&={\\int}p\\pi(p|y_1,\\cdots,y_n)dp \\\\\n",
    "& = {\\int_0^1}\\frac{p^{(k+1)}(1-p)^{(n-k)}}{B(k+1,n-k+1)}dp \\\\\n",
    "& = \\frac{B(k+2,n-k+1)}{B(k+1,n-k+1)}\\\\\n",
    "& = \\frac{k+1}{n+2}\n",
    "\\end{aligned}$$\n",
    "$\\therefore \\displaystyle P(Y=1)=\\frac{k+1}{n+2}$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 思考2\n",
    "通过经验风险最小化推导极大似然估计。证明模型是条件概率分布，当损失函数是对数损失函数时，经验风险最小化等价于极大似然估计。\n",
    "\n",
    "**解答：**\n",
    "\n",
    "假设模型的条件概率分布是$P_{\\theta}(Y|X)$，现推导当损失函数是对数损失函数时，极大似然估计等价于经验风险最小化。\n",
    "极大似然估计的似然函数为：$$L(\\theta)=\\prod_D P_{\\theta}(Y|X)$$两边取对数：$$\\ln L(\\theta) = \\sum_D \\ln P_{\\theta}(Y|X) \\\\ \n",
    "\\mathop{\\arg \\max}_{\\theta} \\sum_D \\ln P_{\\theta}(Y|X) = \\mathop{\\arg \\min}_{\\theta} \\sum_D (- \\ln P_{\\theta}(Y|X))$$ \n",
    "反之，经验风险最小化等价于极大似然估计，亦可通过经验风险最小化推导极大似然估计。"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
